/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.fa;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.TreeMap;

import mosdi.util.Alphabet;
import mosdi.util.BitArray;
import mosdi.util.Iupac;

/** Factory class that provides static method for the construction of CDFAs. */
public class DFAFactory {

	/** Build CDFA from a list of generalized strings by constructing an NFA
	 *  and using the subset construction (bit-parallel implementation). */
	public static CDFA build(Alphabet alphabet, List<GeneralizedString> l) {
		return build(alphabet, l, Integer.MAX_VALUE);
	}

	public static CDFA buildFromIupacPattern(String pattern) {
		return buildFromIupacPattern(pattern, false, Integer.MAX_VALUE);
	}

	public static CDFA buildFromIupacPattern(String pattern, boolean considerReverse) {
		return buildFromIupacPattern(pattern, considerReverse, Integer.MAX_VALUE);
	}
	
	public static CDFA buildFromIupacPattern(String pattern, boolean considerReverse, int nodeLimit) {
		return build(Alphabet.getDnaAlphabet(), Iupac.toGeneralizedStrings(pattern, considerReverse), nodeLimit);
	}
	
	/** Build CDFA from a list of generalized strings by constructing an NFA
	 *  and using the subset construction (bit-parallel implementation). 
	 *  @param nodeLimit If given limit is exceeded, a NodeLimitExceededException is thrown.
	 */
	public static CDFA build(Alphabet alphabet, List<GeneralizedString> l, int nodeLimit) {
		return build(alphabet, new GeneralizedStringsNFA(l), nodeLimit);
	}
	
	public static CDFA build(Alphabet alphabet, NFA nfa, int nodeLimit) {
		TreeMap<BitArray, Integer> dfaNodes = new TreeMap<BitArray, Integer>();
		ArrayList<int[]> transitionTable = new ArrayList<int[]>(512);
		ArrayList<Integer> outputTable = new ArrayList<Integer>(512);
		
		// states still to be build along with their subsets
		Stack<Integer> toBuild = new Stack<Integer>(); 
		Stack<BitArray> toBuildSubset = new Stack<BitArray>();
		// add first node
		BitArray state = nfa.startStates();
		dfaNodes.put(state,0);
		outputTable.add(-1);
		transitionTable.add(null);
		toBuild.push(0);
		toBuildSubset.push(state);
		
		while (!toBuild.isEmpty()) {
			int node = toBuild.pop();
			BitArray subset = toBuildSubset.pop();
			outputTable.set(node, nfa.matchCount(subset));
			// transition list to be filled in the following
			int[] nodeTransitions = new int[nfa.alphabetSize()];
			// for all characters check/add the resulting state
			for (int c=0; c<nfa.alphabetSize(); ++c) {
				BitArray targetSubset = nfa.transition(subset, c); 
				Integer targetNode = dfaNodes.get(targetSubset);
				if (targetNode==null) {
					targetNode = new Integer(outputTable.size());
					if (dfaNodes.size()>=nodeLimit) {
						throw new NodeLimitExceededException();
					}
					dfaNodes.put(targetSubset, targetNode);
					outputTable.add(-1);
					transitionTable.add(null);
					toBuild.push(targetNode);
					toBuildSubset.push(targetSubset);
				}
				nodeTransitions[c]=targetNode;
			}
			transitionTable.set(node, nodeTransitions);
		}
		return new CDFA(alphabet, transitionTable, outputTable);		
	}
	
	
}
